1. Field of the Invention
The present invention relates to computer graphics, and more particularly, to a method and apparatus that adaptively prioritizes objects in a 3-D virtual environment for low-latency streaming.
2. Description of the Related Art
Interactive computer graphics systems produce realistic-looking, three-dimensional models and are useful for applications such as architectural and mechanical CAD, flight simulation, and virtual reality. Such graphics systems typically include a computer workstation that displays images of a three-dimensional model on a video screen as seen from a simulated observer's viewpoint that can be interactively controlled by a user. It is generally desired that such graphics systems maintain an interactive frame rate that is substantially constant (e.g., ten frames per second).
Complex three-dimensional models consist of hundreds or thousands of objects, for example, a model of a house with dozens of rooms, each containing different furnishings. As the simulated observer's interactive viewpoint changes (e.g. moving from room to room and moving closer to certain furnishings), objects can enter or leave the simulated field of view, or can be occluded from view by other objects. Objects are typically modeled offline by a modeling process, and consist of tesselated polygonal approximations or meshes. For realistic representation, modeled objects can contain thousands of polygons, each of which must be rendered independently on a display. Accordingly, the realistic representation of all objects in a scene at desired constant frame rates, and with changing interactive viewpoint, is beyond the capabilities of conventional interactive computer graphics systems.
Techniques have been developed to reduce the processing required to render a virtual environment within the desired frame rates. For example, it is not necessary to render objects that are not visible to a hypothetical viewer in the environment, so such objects can be culled from the scene to be represented. This reduces processing requirements without degrading accuracy. However, for complex virtual environments, the processing savings from culling non-visible objects are not sufficient to maintain the desired interactive frame rates.
For further efficiency, detail elision techniques establish a heirarchy of objects within a field of view, each with a number of levels of detail (corresponding to the number of polygons that have to be rendered, for example). Some objects are rendered at higher levels of detail than other objects, thus further reducing processing requirements. Heuristics are employed to determine which object should be rendered at what level of detail, for example, rendering apparently closer or larger objects at higher levels of detail than objects that are far away or which occupy less screen area. Such heuristics are designed to reduce the number of polygons associated with the object that need to be rendered without substantially reducing image quality. The heuristics can be static, that is, having a constant set of thresholds from frame to frame, or they can be adaptive, where the thresholds are adjusted dynamically in accordance with a target parameter such as frame rate.
In a paper entitled "Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments," Computer Graphics Proceedings (SIGGRAPH '93), pp. 247-254 (1993), Funkhouser and Sequin teach a predictive algorithm for prioritizing objects in a scene using adaptive heuristics so as to produce the "best" image possible within a target frame rate time. For each frame, the available levels of detail of each potentially visible object in a scene are tagged with a benefit (e.g. contribution to overall image quality) and a cost (e.g. contribution to overall rendering time). The total cost of rendering all objects can not exceed the target frame time, and the chosen level of detail for each object is that which results in the highest benefit/cost ratio. This algorithm purportedly achieves near uniform frame times for all observer viewpoints while optimizing the qualitative human visual perception of the scene.
However, many challenges remain that are not addressed by conventional techniques.
Like many conventional assessment algorithms, Funkhouser requires all object data and level of detail information to be available to it in order to fully assess the benefits gained by rendering certain objects at levels of detail greater than other objects. In a server-client configuration, where object data is stored on the server and where the assessment algorithm executes on a client, this means that all object data and level of detail information must be previously transmitted from the server to the client before assessment processing begins. For complex graphical scenes, with large numbers of objects, this requires substantial transmissions of data and requests between server and client. Moreover, since the algorithm operates on all data associated with all of the objects, substantial processing power is required.
Conventional assessment algorithms also fail to account for many factors that affect visual richness of a scene. For example, visual latency is an important factor that is not addressed. Visual latency is a measure of the time between when an object first becomes visible in a scene to when it is rendered in full detail. Simply put, the visual latency of important objects in a scene affects the overall visual richness of the scene more than the visual latency of less important objects. Put another way, reducing latency for important objects causes the overall visual richness of the scene to appear to improve quicker than just elevating their level of detail over less important objects.
The importance of latency is further pronounced in a network environment, for example, where object data must be transmitted from a server to a client, and where objects move in and out of scenes and become less or more important within scenes in response to changing viewpoints within the virtual environment. Since the channel between the server and client typically has a limited bandwidth, simply prioritizing objects within a scene based on the time required to render each object, as performed by Funkhouser, does not consider the costs associated with requesting and transmitting object data between the server and client. In particular, if the available bandwidth is consumed by requests and transmissions of data for less important objects at the expense data for more important objects, the visual richness of the scene will suffer even if the less important objects are rendered at lesser detail. Moreover, requests and transmissions of object data should keep in step with the changing viewpoint, as different objects become more important to the scene, so that the latency of important objects is kept to a minimum.
Another factor that is not accounted for by conventional assessment algorithms is viewer turn rate. Some algorithms attach more importance to objects appearing at the center of the screen than those appearing outside the center. Meanwhile, however, when a simulated observer's viewpoint is turning within the scene, the user who is commanding such movement will tend to be more interested in objects that are in the direction of the turn. Such an interest will be further in proportion to the rate at which the viewpoint is turning. Accordingly, higher priority should be given to those objects in the direction of the turn in proportion to the rate of the turn.
Therefore, there remains a need for an implementation for prioritizing objects within 3D virtual environments and for managing the streaming of the objects in response to changing viewpoints that effectively addresses these challenges. The present invention fulfills this need.